// https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/
class Solution {
    int[] tmp;
    public int reversePairs(int[] record) {
        tmp=new int[record.length];
        return mergeSort(record,0,record.length-1);
    }
    public int mergeSort(int[] nums,int left,int right) {
        if(left>=right) return 0;
        int mid=(left+right)/2;
        int ret=0;// 逆序对的数量
        ret+=mergeSort(nums,left,mid);
        ret+=mergeSort(nums,mid+1,right);
        // 开始合并
        int cur1=left;
        int cur2=mid+1;
        int k=0;
        while(cur1<=mid && cur2<=right) {
            if(nums[cur1]<=nums[cur2]) {
                tmp[k++]=nums[cur1++];
            } else {
                tmp[k++]=nums[cur2++];
                ret+=(mid-cur1+1);
            }
        }
        while(cur1<=mid) {
            tmp[k++]=nums[cur1++];
        }
        while(cur2<=right) {
            tmp[k++]=nums[cur2++];
        }
        for(int j=left;j<=right;j++) {
            nums[j]=tmp[j-left];
        }
        return ret;
    }
}
public class Shuzuzhongdnixuduishuliang {
}
